/**
 * skiplist.c
 * skiplist 简易实现
 * 
 * 竹影半墙
 * 2023.08
 */
#include "base.h"
#include "pageca.h"
#include "skiplist.h"

#define SKL_STEP_MIN    (2)
#define SKL_LEVEL_MIN   (1)
#define SKL_LEVEL_MAX   (64)

#define SKL_LEVEL_BITS  (6)
#define SKL_LEVEL_SHIFT (64-SKL_LEVEL_BITS)

#define SKL_CACHE_BITS  (1)
#define SKL_CACHE_SHIFT (64-SKL_HOLD_BITS)

#define SKL_HOLD_BITS   (SKL_LEVEL_BITS+SKL_CACHE_BITS)

#define SKL_NEXT_BITS   (64-SKL_HOLD_BITS)
#define SKL_NEXT_MASK   ((1ull<<SKL_NEXT_BITS)-1)

#define SKL_LPL(lv)     ({lv-1;})
#define skl_max(a,b)    ({(a)>(b) ? (a) : (b);})
#define skl_min(a,b)    ({(a)<(b) ? (a) : (b);})

#if 0
#endif
struct skl_node {
    uint64_t next;
    void *lp[];
};

static __always_inline void 
skl_node_next_clear(struct skl_node *n)
{
    n->next = 0;
    return ;
}

static __always_inline 
size_t skl_node_size(int level, int exts)
{
    size_t size = sizeof(struct skl_node);
    size += (level-1)*sizeof(void*)+ exts;
    return size;
}

static __always_inline void 
skl_node_next_addr_set(void *a, void *n)
{
    uint64_t next = *(uint64_t*)a;

    next &= ~SKL_NEXT_MASK;
    next |= (uintptr_t)n & SKL_NEXT_MASK;
    *(uint64_t*)a = next;
    return ;
}

static __always_inline void 
skl_node_next_set(struct skl_node *n, void *next)
{
    skl_node_next_addr_set(&n->next, next);
    return ;
}

static __always_inline 
struct skl_node * skl_node_next_get(struct skl_node *n)
{
    return (struct skl_node*)(n->next & SKL_NEXT_MASK);
}

static __always_inline 
void skl_node_level_set(struct skl_node *n, int level)
{
    n->next |= (uint64_t)(unsigned)level << SKL_LEVEL_SHIFT;
}

static __always_inline 
int skl_node_level_get(struct skl_node *n)
{
    return n->next >> SKL_LEVEL_SHIFT;
}

static __always_inline void 
skl_node_cache_set(struct skl_node *n)
{
    n->next |= 1ull << SKL_CACHE_SHIFT;
    return ;
}

static __always_inline 
bool skl_node_cache_get(struct skl_node *n)
{
    return n->next & (1ull << SKL_CACHE_SHIFT);
}

static __always_inline 
void * skl_node_extend(struct skl_node *n)
{
    void *a;
    int level;

    level = skl_node_level_get(n);
    a = (char*)n + sizeof(*n) + (level-1)*sizeof(void*);
    return a;
}

static __always_inline struct skl_node * 
skl_node_after(struct skl_node *n, int level)
{
    if (level)
        return n->lp[SKL_LPL(level)];
    return skl_node_next_get(n);
}

#if 0
#endif
struct skl {
    int (*compar)(const void *s, const void *u);
    unsigned seed;
    int exts;
    int step;
    int lmax;
    int (*set)(const void *s, const void *u);
    void *(*clear)(void *u);
    void *next;
    struct skl_node head;
};

static __always_inline void ** 
skl_extend_addr(struct skl *skl, int level)
{
    void **a;

    a = (void **)skl_node_extend(&skl->head);
    a += level - 1;
    return a;
}

static __always_inline struct pageca * 
skl_extend(struct skl *skl, int level)
{
    void **a = skl_extend_addr(skl, level);
    return (struct pageca *) *a;
}

static __always_inline void 
skl_next_set(struct skl *skl, struct skl_node *n)
{
    skl_node_next_set(&skl->head, n);
    return ;
}

static __always_inline 
struct skl_node * skl_next_get(struct skl *skl)
{
    return skl_node_next_get(&skl->head);
}

static __always_inline void 
skl_level_set(struct skl *skl, int level)
{
    skl_node_level_set(&skl->head, level);
    return ;
}

static __always_inline 
int skl_level_get(struct skl *skl)
{
    return skl_node_level_get(&skl->head);
}

static __always_inline void 
skl_cache_set(struct skl *skl)
{
    skl_node_cache_set(&skl->head);
    return ;
}

static __always_inline void 
skl_next_clear(struct skl *skl)
{
    skl_node_next_clear(&skl->head);
    return ;
}

static __always_inline 
bool skl_cache_get(struct skl *skl)
{
    return skl_node_cache_get(&skl->head);
}

#if 0
#endif
static struct pageca skl_ca;
static struct pageca skl_pca_ca;

static __always_inline struct skl * skl_palloc(void)
{
    return (struct skl*)pca_alloc(&skl_ca);
}

static __always_inline void 
skl_pfree(struct skl *skl)
{
    pca_free(&skl_ca, skl);
    return ;
}

static 
__always_inline struct pageca * skl_pca_palloc(void)
{
    return (struct pageca*)pca_alloc(&skl_pca_ca);
}

static __always_inline void
skl_pca_pfree(struct pageca *pa)
{
    pca_free(&skl_pca_ca, pa);
    return ;
}

static __always_inline 
struct skl * skl_malloc(size_t size)
{
    return (struct skl*)malloc(size);
}

static __always_inline void 
skl_mfree(struct skl *skl)
{
    free(skl);
    return ;
}

static __always_inline 
struct skl_node * skl_node_palloc(struct pageca *pa)
{
    return (struct skl_node*)pca_alloc(pa);
}

static __always_inline void 
skl_node_pfree(struct pageca *pa, struct skl_node *n)
{
    pca_free(pa, n);
    return ;
}

static __always_inline 
struct skl_node * skl_node_malloc(size_t size)
{
    return (struct skl_node*)malloc(size);
}

static __always_inline void 
skl_node_mfree(struct skl_node *n)
{
    free(n);
    return ;
}

#if 0
#endif
static int skl_app_adjust(struct skl_app *app)
{
    int step  = app->step;
    int level = app->level;

    if (!app->compar)
        return -1;
    level = skl_max(level, SKL_LEVEL_MIN);
    level = skl_min(level, SKL_LEVEL_MAX);
    step  = skl_max(step,  SKL_STEP_MIN);

    app->level = level;
    app->step  = step;
    return 0;
}

static struct skl * skl_alloc(struct skl_app *app)
{
    int level;
    struct skl *skl;
    size_t size = sizeof(*skl);

    level = app->level - 1;
    size += level * sizeof(void*);
    size += sizeof(struct pageca*) * (level+1);

    if (app->around &&
        size == pca_size(&skl_ca)) {
        skl = skl_palloc();
        if (!skl)
            return skl;
        skl_next_clear(skl);
        skl_cache_set(skl);
    } else {
        skl = skl_malloc(size);
        if (!skl)
            return skl;
        skl_next_clear(skl);
    }
    skl_level_set(skl, level+1);
    size -= sizeof(*skl);
    memset(skl+1, 0, size);
    return skl;
}

struct skl_distr {
    uint32_t max;
    uint16_t size;
};

static void 
skl_node_distribute(struct skl_distr dstr[], int level, struct skl_app *app)
{
    uint32_t dstred;
    int exts;
    unsigned around;
    float base;
    int i = 1;

    base = (float)1/app->step;
    around = app->around;
    exts = app->exts;
    dstred = 0;
    for (/* none */; i < level; ++i) {
        dstr[i].max = around * powf(base, i);
        dstr[i].size = skl_node_size(i+1, exts);
        dstred += dstr[i].max;
    }
    dstr[0].max  = around - dstred;
    dstr[0].size = skl_node_size(1, exts);
    return ;
}

static void skl_cache_init(struct skl *skl, struct skl_app *app)
{
    void **a;
    struct pageca *pa;
    struct skl_distr dstr[SKL_LEVEL_MAX];
    int i, level;

    if (!skl_cache_get(skl))
        return ;

    level = skl_level_get(skl);
    skl_node_distribute(dstr, level, app);
    for (i = 0; i < level; ++i) {
        pa = skl_pca_palloc();
        if (!pa)
            break;
        pca_app(pa, dstr[i].size, dstr[i].max);
        pca_init(pa);
        a  = skl_extend_addr(skl, i + 1);
        *a = pa;
    }
    return ;
}

static int skl_level_rand(struct skl *skl)
{
    int lmax;
    int step;
    int level = 1;

    step = skl->step;
    lmax = skl_level_get(skl);
    while (!(rand_r(&skl->seed) % step)) {
        if (level >= lmax)
            break;
        level += 1;
    }
    return level;
}

static struct skl_node * skl_node_alloc(struct skl *skl, int level)
{
    int size;
    struct skl_node *n;
    struct pageca *pa;

    if (skl_cache_get(skl)) {
        pa = skl_extend(skl, level);
        n = skl_node_palloc(pa);
        if (!n)
            return n;
        skl_node_next_clear(n);
        skl_node_cache_set(n);
        skl_node_level_set(n, level);
        return n;
    }

    size = skl_node_size(level, skl->exts);
    n = skl_node_malloc(size);
    if (!n)
        return n;
    skl_node_next_clear(n);
    skl_node_level_set(n, level);
    return n;
}

static void skl_node_free(struct skl *skl, struct skl_node *n)
{
    struct pageca *pa;
    int level;

    if (!skl_node_cache_get(n)) {
        skl_node_mfree(n);
        return ;
    }

    level = skl_node_level_get(n);
    pa = skl_extend(skl, level);
    skl_node_pfree(pa, n);
    return ;
}

static inline void * skl_lp_addr(struct skl_node *n, int level)
{
    if (!level)
        return &n->next;
    return (void*)((void**)n->lp + SKL_LPL(level));
}

static void 
skl_level_expand(struct skl *skl, void *prev[], int level)
{
    int lmax = skl->lmax;

    while (level > lmax) {
        prev[lmax] = skl_lp_addr(&skl->head, lmax);
        lmax += 1;
    }
    skl->lmax = lmax;
    return ;
}

static void * 
skl_node_add(struct skl *skl, void *prev[], struct skl_node *n, const void *u)
{
    int level;
    void **a;
    void *d;

    d = skl_node_extend(n);
    if (skl->set && skl->set(d, u))
        return NULL;
    level = skl_node_level_get(n);
    skl_level_expand(skl, prev, level);

    while (level--) {
        a = (void**)prev[level];
        if (level) {
            n->lp[SKL_LPL(level)] = *a;
            *a = n;
            continue;
        }
        skl_node_next_set(n, *a);
        skl_node_next_addr_set((void*)a, n);
    }
    return d;
}

static struct skl_node *
skl_find(struct skl *skl, void *prev[], const void *u)
{
    int r;
    void *d;
    struct skl_node *n;
    struct skl_node *p;
    int level = skl->lmax;

    p = &skl->head;
    n = NULL;
    r = -1;

    while (level--) {
        n = skl_node_after(p, level);
        if (!n)
            goto prev_assign;
        d = skl_node_extend(n);
        while ((r=skl->compar(d, u)) < 0) {
            p = n;
            n = skl_node_after(p, level);
            if (!n)
                break;
            d = skl_node_extend(n);
        }
        prev_assign:
        if (!prev && !r)
            break;
        if (!prev)
            continue;
        prev[level] = skl_lp_addr(p, level);
    }
    return n;
}

static void skl_level_shrink(struct skl *skl)
{
    int level = skl->lmax - 1;

    if (level - 1 >= 0 &&
        !skl_node_after(&skl->head, level)) {
        skl->lmax -= 1;
    }
    return ;
}

static void *
skl_node_del(struct skl *skl, void *prev[], struct skl_node *n, const void *u)
{
    struct skl_node *c;
    void **a;
    int level;
    void *d;

    d = skl_node_extend(n);
    if (skl->compar(d, u))
        return NULL;
    d = skl->clear ?
        skl->clear(d) : NULL;

    level = skl_node_level_get(n);
    while (level--) {
        a = (void**)prev[level];
        if (level) {
            *a = n->lp[SKL_LPL(level)];
            skl_level_shrink(skl);
            continue;
        }
        c = skl_node_next_get(n);
        skl_node_next_addr_set((void*)a, c);
    }
    skl_node_free(skl, n);
    return d;
}

#if 0
#endif
struct skl * skl_init(struct skl_app *app)
{
    struct skl *skl;

    if ((skl_app_adjust(app))||
       !(skl =skl_alloc(app)))
        return NULL;
    skl->compar = app->compar;
    skl->step = app->step;
    skl->seed = (uintptr_t)skl;
    skl->exts = app->exts;
    skl->lmax = 1;
    skl->set = app->set;
    skl->clear = app->clear;
    skl->next = NULL;
    skl_cache_init(skl, app);
    return skl;
}

void skl_close(struct skl *skl)
{
    struct pageca *pa;
    int i, level;

    if (!skl_cache_get(skl)) {
        skl_mfree(skl);
        return ;
    }
    level = skl_level_get(skl);
    for (i = 0; i < level; ++i) {
        pa = skl_extend(skl, i+1);
        pca_close(pa);
        skl_pca_pfree(pa);
    }
    skl_pfree(skl);
    return ;
}

void * skl_add(struct skl *skl, const void *u)
{
    struct skl_node *n;
    void *d;
    int r;
    void *prev[SKL_LEVEL_MAX];

    (void)skl_find(skl, prev, u);
    r = skl_level_rand(skl);
    n = skl_node_alloc(skl, r);
    if (!n)
        return n;
    d = skl_node_add(skl, prev, n, u);
    if (!d)
        skl_node_free(skl, n);
    return d;
}

void * skl_get(struct skl *skl, const void *u)
{
    void *n;

    n = skl_find(skl, NULL, u);
    if (!n)
        return n;
    return skl_node_extend(n);
}

void * skl_del(struct skl *skl, const void *u)
{
    void *d;
    struct skl_node *n;
    void *prev[SKL_LEVEL_MAX];

    n = skl_find(skl, prev, u);
    if (!n)
        return n;
    d = skl_node_del(skl, prev, n, u);
    return d;
}

void * skl_seek_first(struct skl *skl)
{
    struct skl_node *n;
    void *d = NULL;

    n = skl_next_get(skl);
    if (n)
        d = skl_node_extend(n);
    skl->next = n;
    return d;
}

void * skl_seek(struct skl *skl, const void *u)
{
    struct skl_node *n;
    void *d = NULL;

    n = skl_find(skl, NULL, u);
    if (n)
        d = skl_node_extend(n);
    skl->next = n;
    return d;
}

void * skl_next(struct skl *skl)
{
    struct skl_node *n;
    void *d = NULL;

    n = skl->next;
    if (n) {
        d = skl_node_extend(n);
        n = skl_node_next_get(n);
        skl->next = n;
    }
    return d;
}

void skl_init_ca(struct skl_cache *ca)
{
    uint16_t size;
    int level = ca->skl_level;

    if (level <= 0 ||
        !ca->n_skl || !ca->n_cache)
        return ;
    size = sizeof(struct skl);
    size += sizeof(void*) * (level-1);
    size += sizeof(struct pageca*) * level;
    pca_app(&skl_ca, size, ca->n_skl);
    pca_init(&skl_ca);

    size = sizeof(struct pageca);
    pca_app(&skl_pca_ca, size, ca->n_cache);
    pca_init(&skl_pca_ca);
    return ;
}

void skl_close_ca(void)
{
    pca_close(&skl_ca);
    pca_close(&skl_pca_ca);
    return ;
}